package com.itheima.algorithm.sort;

import java.util.ArrayList;

public class E03Leetcode164_2 {
    public int maximumGap(int[] nums){
        // 1.处理特殊情况
        if (nums.length < 2) {
            return 0;
        }
        // 2.基数排序
        // 寻找最大值
        int max = nums[0];
        for (int i=0;i<nums.length;i++){
            max = Math.max(max, nums[i]);
        }
        ArrayList<Integer>[] buckets = new ArrayList[10];
        for (int i=0;i<10;i++){
            buckets[i] = new ArrayList<>();
        }
        int m= 1;
        while (m <= max){
            for (int i:nums){
                buckets[i /m % 10].add(i);
            }
            int k = 0;
            for (ArrayList<Integer> bucket :buckets){
                for (Integer i:bucket){
                    nums[k++] = i;
                }
                bucket.clear();
            }
            m*=10;
        }
        // 3.寻找最大差值
        int r = 0;
        for (int i=1;i<nums.length;i++){
            r = Math.max(r,nums[i] - nums[i - 1]);
        }
        return r;
    }

    public static void main(String[] args) {
        int[] nums = {26, 16, 13, 11, 100000};
        int r = new E03Leetcode164_2().maximumGap(nums);
        System.out.println(r);
    }
}
